/********************************************************************************************************************************
 * 单链表
 * 
 * 线性表的链式存储
 * 
 ********************************************************************************************************************************/
#include <cstdlib>
#include <cstdio>

/**
 * 单链表中结点类型的描述
 * */
typedef int ElemType;                        //定义元素的类型

typedef struct LNode{                       //定义单链表的结点类型
    ElemType data;                          //数据域
    struct LNode *next;                     //指针域
}LNode,*LinkList;

/********************************************************************************************************************************
 * 
 * 带头结点的单链表
 * 
 * */

/**
 * 采用头插法建立单链表
 * 
 * 思想：
 *      1）每次将新结点插到最前端
 * 
 * 补充
 *      1）申明头指针 LNode * L 等价于 LinkList L 后者可读性更高
 * */
LinkList List_HeadInsert(LinkList &L){          //逆向建立单链表
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));        //创建头结点
    L->next = NULL;                             //初始为空链表
    scanf("%d",&x);                             //输入结点的值
    while(x != 9999){                           //输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));     //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;                            //将新结点插入到表中，L为头指针

        scanf("%d",&x);
    }

    return L;
}

/**
 * 采用尾插法建立单链表
 * 
 * 思想：
 *      1）每次将新结点插入到当前链表的表尾
 *      2）设置一个尾指针r,每次指向当前链表的尾结点
 * */
LinkList List_TailInsert(LinkList &L){          //正向建立单链表

    int x;                                      //设元素类型为整型
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r = L;                            //r为表尾指针
    scanf("%d",&x);                             //输入结点的值
    while(x != 9999){                           //输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;                                  //r指向新的表尾结点

        scanf("%d",&x);
    }

    r->next = NULL;                             //尾结点指针置空

    return L;

}

/**
 * 初始化一个单链表
 * */
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L == NULL)
        return false;

    L->next = NULL;
    return true;
}

/**
 * 判断一个单链表是否为空
 * */
bool Empty(LinkList L){
    return (L->next == NULL);
}

/**
 * 求表的长度
 * */
int Length(LinkList L){
    int len = 0;                                //统计表长
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }

    return len;
}

/**
 * 按位查找,返回第i个元素
 * */
LNode *GetElem(LinkList L,int i){
    if(i < 0)                                   //若i无效，则返回NULL
        return NULL;
    int j = 0;                                  //当前p指向的是第几个结点
    LNode* p = L;                               //指针p指向当前扫描到的结点
    while(p && j < i){                          //从第一个结点开始找，查找第i个结点
        p = p->next;
        j++;
    }

    return p;                                   //返回第i个结点的指针，若i大于表长，则返回NULL                                             
}

/**
 * 按值查找：找到数据域 == e 的结点
 * */
LNode *LocateElem(LinkList L, ElemType e){
    LNode *p = L->next;
    while(p != NULL && p->data != e){           //从第1个结点开始查找data域为e的结点
        p = p->next;
    }

    return p;                                   //找到后返回该结点的指针，否则返回NULL
}

/**
 * 插入结点操作
 * 
 * 插入到单链表的第i个位置
 * */
bool ListInsert(LinkList &L,int i,ElemType x){
    if(i < 1)                                   //检查插入位置下限的合法性
        return false;
    
    LNode *p;                                   //指针p指向当前扫描到的结点
    int j = 0;                                  //当前p指向的是第几个结点
    p =  L;                                     //L指向头结点，投机诶单是第0个结点
    while(p != NULL && j < i - 1){              //循环找到第i - 1 个结点; 当 i 的值超出范围即p == NULL 时
        p = p->next;
        j++;
    }    
    if(p == NULL)                               //处理上限问题：当 i 的值超出上限时，p == NULL
        return false;              

    LNode *s = (LNode *)malloc(sizeof(LNode));  //创建新结点
    s->data = x;
    LNode *p = GetElem(L, i - 1);               //查找插入位置的前驱结点
    s->next = p->next;                          //设置后继结点
    p->next = s;                                //设置前驱结点

    return true;
}

/**
 * 后插操作 ： 在p结点之后插入元素e
 * */
bool InsertNextNode(LNode *p, ElemType e){
    if(p == NULL)
        return false;
    LNode *s = (LNode * )malloc(sizeof(LNode));
    if(s == NULL)                               //内存分配失败
        return false;
    s->data = e;                                //用结点s 保持数据元素e
    s->next = p->next;
    p->next = s;                                //将结点s连到p之后

    return true;
}

/**
 * 前插操作： 在p结点之前插入元素e
 * 
 * 思路 ： 
 *      1)先在p结点后建立结点，进行后插操作，然后交换p 和 p之后结点s 的数值域
 * */
bool InsertPriorNode(LNode *p,ElemType e){
    if(p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));  //创建新结点
    if(s == NULL)                               //内存分配失败
        return false;
    s->next = p->next;
    p->next = s;                         
    s->data = p->data;                          //交换数据域部分
    p->data = e;

    return true;
}

/**
 * 按位序删除结点操作
 * 
 * 将单链表的第i个结点删除
 * */
bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i < 1)                                   //检查插入位置下限的合法性
        return false;
    
    LNode *p;                                   //指针p指向当前扫描到的结点
    int j = 0;                                  //当前p指向的是第几个结点
    p =  L;                                     //L指向头结点，投机诶单是第0个结点
    while(p != NULL && j < i - 1){              //循环找到第i - 1 个结点; 当 i 的值超出范围即p == NULL 时
        p = p->next;
        j++;
    }    
    if(p == NULL || p->next == NULL)            //处理上限问题：当 i 的值超出上限时，p == NULL and 当p的后面没有结点时，无法删除i结点
        return false; 
        
    LNode *q = p->next;                         //令q指向被删除结点
    e = q->data;
    p->next = q->next;                          //将*q 结点从链中删除
    free(q);                                    //释放结点的存储空间

    return true;
}

/**
 * 删除结点 *p
 * 
 * BUG:
 *      1)当 p 为最后一个结点时，由于p->next == NULL,则会出现空指针异常的错误
 * */
bool DeleteNode(LNode *p){
    if(p == NULL)
        return false;

    LNode *q = p->next;                         //令q 指向 *p 的后继结点
    p->data = p->next->data;                    //和后继结点交换数据域
    p->next = q->next;                          //将*q 结点从链中删除
    free(q);                                    //释放后继结点的存储空间

    return true;
}



/**
 * 
 * */

/********************************************************************************************************************************
 * 
 * 测试程序
 * 
 * */
void test(){
    LinkList L;         //申明一个指向单链表的指针

    InitList(L);        //初始化
}


